#! /usr/bin/env python
# -*- coding: utf-8 -*-

from collections import defaultdict


class Solution:
    # @param {int} n an integer
    # @return {tuple[]} a list of tuple(sum, probability)
    def dicesSum(self, n):
        self.sum_prop = {}      # {n : n's props}
        self.sum_prop[0] = {}
        self.sum_prop[1] = { i: 1/float(6) for i in range(1, 7)}

        self.prob(n)

        return self.sort(n)
        # return self.sum_prop[n]

    def prob(self, n):
        if n in self.sum_prop:
            return

        a = n // 2
        b = n - a

        self.prob(a)
        self.prob(b)

        self.comb_a_b(a, b)

    def comb_a_b(self, a, b):
        assert a in self.sum_prop
        assert b in self.sum_prop

        sum = a+b
        assert sum not in self.sum_prop

        self.sum_prop[sum] = defaultdict(float)
        for sum_a, prop_a in self.sum_prop[a].items():
            for sum_b, prop_b in self.sum_prop[b].items():
                self.sum_prop[sum][sum_a + sum_b] += prop_a * prop_b

        # for sum_a in self.sum_prop[a]:
        #     for sum_b in self.sum_prop[a]:
        #         self.sum_prop[sum_a + sum_b] = self.sum_prop[a][sum_a]


    def sort(self, n):
        assert n in self.sum_prop
        d = self.sum_prop[n]

        l = sorted(d)

        # return [(ele, d[ele]) for ele in d]
        return [(ele, self.truncate(d[ele])) for ele in d]

    def truncate(self, f, n=2):
        # 因为精度问题, 始终无法通过round(0.125) == 0.12
        # python2 测试通过
        return round(f+0.0001, n)
        base = 10 ** n
        f = int(f*base)
        f /= base
        return f


def main():
    from pprint import pprint

    print("start main")

    s = Solution()
    r = s.dicesSum(3)
    # pprint(dict(r))
    pprint(r)


if __name__ == "__main__":
    main()
